In a conventional router or switch device, next hop (NH) entries typically form fixed chains, and packets are processed by the device as they traverse these chains. A NH entry can either be a non-connected NH entry or a connected NH entry. As used herein, a non-connected NH (non-CNH) entry is a data structure that contains information chaining (i.e., linking) it to another NH entry, and a connected NH (CNH) entry is a data structure that contains information which enables the packets to be forwarded to a connected physical device (i.e., a device that is the immediate next hop in the network).
FIG. 1 illustrates conventional Fast Re-Route (FRR) device 100 comprising of conventional FRR NH entries 101-102. FRR NH entries are commonly referred to as “double barrel” next hop entries because each FRR NH entry references two other next hop entries: a primary next-hop entry and a backup next-hop entry, which is used when the primary chain fails. As used herein, one NH entry “referencing” another NH entry refers to a NH entry containing an identifier/pointer that maps/points (i.e., references) another NH entry. In FIG. 1, FRR NH entry 101 includes Forwarding Information Base (FIB) NH entry 111 that references non-CNH entry 112, which in turn references CNH entry 113. NH entries 111-113 comprise the primary chain. FRR NH entry 101 also includes FIB NH entry 115 that references non-CNH entry 116, which in turn references CNH entry 117. NH entries 115-117 comprise the backup chain, which is used when the primary chain (i.e., NH entries 111-113) fails. Similarly, FRR NH entry 102 includes FIB NH entry 121 that references non-CNH entry 122, which in turn references CNH entry 123. NH entries 121-123 comprise the primary chain. FRR NH entry 102 also includes FIB NH entry 125 that references non-CNH entry 126, which in turn references CNH entry 127. NH entries 125-127 comprise the backup chain, which is used when the primary chain (i.e., NH entries 121-123) fails. It should be noted that there can be zero or more non-CNH entries in any given chain. For example, FIB NH entry 111 can reference CNH entry 113 directly, without having to reference non-CNH entry 112. By way of further example, non-CNH entry 112 can alternatively reference another non-CNH entry instead of directly referencing CNH entry 113 as illustrated in FIG. 1.
When switching from the primary chain to the backup chain (e.g., performing a failover), or vice versa, the device needs to be programmed with the correct next-hop entry that is to be used. This is not a problem when the number of FRR-NH entries is small. However, when a single event causes the switching of hundreds of thousands of FRR NH entries, it can take many seconds to reprogram the device with the new next-hop information. For example, when hundreds of thousands of NH entries contain forwarding information that causes network traffic to be sent to a same link (e.g., a Layer 3 (L3) Link Aggregation (LAG) link), and that same link fails, each and every one of the hundreds of thousands of NH entries need to be individually re-programmed in order for traffic to be diverted/redirected to another link. Such a reconvergence mechanism is very time consuming and can result in loss of traffic.